# 二叉树的右视图： https://leetcode-cn.com/problems/binary-tree-right-side-view/submissions/

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        """
            我觉得可以以 ： 根， 右， 左的方式进行深度遍历
            每层第一个加载的 节点，一定是最右的！,记录它。
        """
        if not root: return []
        rst = []
        def traversal(node, deep):
            if not node: return 

            # 小于说明还没这层， 加进去
            if len(rst) < deep:
                rst.append(node.val)

            traversal(node.right, deep + 1)
            traversal(node.left, deep + 1)

        traversal(root, 1)
        return rst


# 也可以使用层序遍历， 找到每层最右侧的节点
from collections import deque
class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        """
            使用层序遍历，记录每层最右侧节点的值
        """
        if not root: return []
        queue = deque()
        queue.append(root)
        rst = []
        while queue:
            n = len(queue)
            for i in range(n):
                node = queue.popleft()
                if i == n - 1: 
                    rst.append(node.val)
                
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            
        return rst


